1 Astrazione nella programmazione

1.1 Cittadini

Le entità di un linguaggio di programmazione possono essere:

Denotabili, se possono essere associati ad un nome
Esprimibili, se possono essere il risultato di un’espressione complessa
Memorizzabili, se possono essere memorizzati in una variabile

	Denotabile	Esprimibile	Memorizzabile
Prima classe	SI	SI	SI
Seconda classe	SI	SI	NO
Terza classe	SI	NO	NO

1.2 Astrazione di funzione

Un’astrazione di funzione include un’espressione da valutare, e quando chiamata, darà un valore come risultato.

Un’astrazione di funzione è descritta nel seguente modo:

function I(FP1; …; FPn) is E

dove I è un identificatore, FP_1, …, FP_n sono parametri formali, ed E è l’espressione da valutare che ha la proprietà di dare un risultato ogni qualvolta è chiamata con argomenti appropriati.

Una chiamata di funzione, I(AP_1; …; AP_n) dove i parametri effettivi, AP_1; …; AP_n, determinano gli argomenti, ha due punti di vista:

Utente: la chiamata di una funzione trasforma gli argomenti in un risultato;
Implementatore: la chiamata valuta E, avendo precedentemente vincolato i parametri formali agli argomenti corrispondenti.

E’ naturale attendersi che il corpo della funzione non includa dei comandi il cui effetto è quello di cambiare lo stato di un sistema, ma, Pascal, Ada e altri linguaggi di programmazione permettono di avere comandi nel corpo di funzioni per poter sfruttare la potenza espressiva dell’assegnazione e dell’iterazione. Diversamente saremmo costretti a esprimere ricorsivamente le espressioni da valutare, che può essere fonte di inefficienze nell’uso delle risorse di calcolo. Si lascia al programmatore il compito di utilizzare correttamente i comandi in modo da evitare side effects.

In alcuni linguaggi (Fortran) le funzioni sono di terza classe, in altri (Pascal) sono di seconda classe, mentre in linguaggi funzionali (Lisp, ML) sono di prima classe.

1.3 Astrazione di procedura

Un’astrazione di procedura include un comando da eseguire, e quando chiamata, aggiornerà le variabili che rappresentano lo stato del sistema.

Un’astrazione di procedura è descritta nel seguente modo:

procedure I(FP1; …; FPn) is C

dove I è un identificatore, FP_1; …; FP_n sono parametri formali, e C è il blocco di comandi da eseguire che gode della proprietà di cambiare lo stato del sistema quando chiamato con argomenti appropriati.

Data una chiamata di procedura, I(AP_1; …; AP_n) dove AP_1; …; AP_n sono i parametri effettivi, vediamo i due punti di vista:

Utente: la chiamata aggiornerà lo stato del sistema in modo dipendente dai parametri
Implementatore: la chiamata consentirà l’esecuzione del corpo di procedura C, avendo precedentemente vincolato i parametri formali agli argomenti corrispondenti.

In Pascal e in C le procedure sono cittadini di seconda classe.

1.4 Funzioni vs Procedure

L’astrazione di funzione o di procedura sono due tecniche di programmazione di supporto all’astrazione funzionale, intesa come tecnica di progettazione del software secondo la quale occorre distinguere la specifica di un operatore (come esso è visto e manipolato dall’utente) dalla sua realizzazione.

Quale sia l’astrazione più opportuna da adottare dipende da:

Tipo di operatore progettato:
- ha effetti collaterali: astrazione di procedura
- non ha effetti collaterali: astrazione di funzione
Limiti imposti dal linguaggio di programmazione

1.5 Astrazione di controllo

L’astrazione di controllo si applica alla classe sintattica struttura di controllo.

Le strutture di controllo definiscono l’ordine in cui le istruzioni devono essere eseguite.

Possiamo specificare un’astrazione di controllo come segue:

control I(FP1; …; FPn) is S

dove I è un identificatore di una nuova struttura di controllo, FP_1; …; FP_n sono parametri formali, e S è una espressione di controllo che definisce un ordine di esecuzione.

Il linguaggio macchina fornisce due semplici meccanismi per governare il flusso di controllo delle istruzioni singole: l’elaborazione in sequenza e il salto. Nei linguaggi assemblativi le istruzioni da eseguire in sequenza sono scritte l’una dopo l’altra, mentre il salto è rappresentato da un’istruzione di jump:

jump to <indirizzo simbolico o label>

L’indirizzo simbolico è comunque un dettaglio di scarsa importanza per il programmatore: quello che conta è poter indicare le prossime istruzioni da eseguire. Per questa ragione i linguaggi di alto livello hanno introdotto strutture di controllo astratte come la selezione: if cond then S1 else S2

Similmente sono state introdotte diverse strutture di controllo astratte per l’iterazione.

Inoltre l’utilizzo dello stack per conservare gli indirizzi di ritorno dalle chiamate di funzione/procedura si è tradotta nella possibilità di effettuare chiamate ricorsive.

1.6 Astrazione di selettore

L’astrazione di selettore include il calcolo dell’accesso ad una variabile.

Definiamo un’astrazione di selettore con la seguente espressione:

selector I(FP1; …; FPn) is A

dove I è un identificatore, FP_1; …; FP_n sono parametri formali, e A è una espressione che restituisce un accesso a una variabile.

Un linguaggio di programmazione dispone di costrutti per poter accedere ad una variabile. Lo stesso identificatore può essere usato sia come nome di un valore (legame dinamico fra identificatore e valore) e sia come un indirizzo (legame statico fra identificatore e locazione di memoria).

Tuttavia, se osserviamo il seguente codice Pascal:

type queue = ...;  
var Aq: queue;  
function first(q:queue): integer (* restituisce il primo intero della coda *)  
    
i := first(Aq)

Ci accorgiamo che la chiamata first(Aq) può comparire solo alla destra di una assegnazione, perché le funzioni restituiscono valori, mentre a sinistra: first(Aq) := 0; dovrebbe restituire riferimenti ad aree di memoria.

La funzione first(q) mi restituisce il primo intero della coda, mentre il selettore first(q) mi restituisce l’area di memoria in cui è memorizzato il primo intero della coda.

In generale i linguaggi ad alto livello non permettono di definire nuove astrazioni di selettore, tranne ad esempio in C++: con & possiamo definire un’astrazione di selettore:

class Queue {   
    public:  
        static int & first(Queue *);  
};  

int main() {
    Queue q*;  
    int i = first(q);  
    first(q) *= first(q); // valido  
    first(q)++; // valido
}

1.7 Astrazione di tipo

L’espressione di tipo è il costrutto con cui alcuni linguaggi di programmazione consentono di definire un nuovo tipo (esempio: le Struct in C).

L’astrazione di tipo può essere descritta come segue:

type I(FP1; …; FPn) is T

dove I è un identificatore del nuovo tipo, FP_1; …; FP_n sono parametri formali, e T è una espressione di tipo che specificherà la rappresentazione dei dati di tipo I e le operazioni ad esso applicabili.

I limiti delle Struct in C o dei Record in Pascal sono i seguenti:

Il programmatore non può definire nuovi operatori specifici da associare al tipo.
Violazione del requisito di protezione: l’utilizzatore è consapevole della rappresentazione del tipo e quindi è in grado di operare direttamente sulla rappresentazione
L’astrazione di tipo non è parametrizzata

Il problema può essere risolto mediante un costrutto di programmazione che permette di incapsulare rappresentazioni del dato e operatori leciti. Questo costrutto di programmazione è il package, ovvero un gruppo di componenti dichiarate, come tipi, costanti, variabili, funzioni e persino (sotto) moduli.

1.8 Astrazione generica

Un’astrazione generica è un’astrazione su una dichiarazione la cui chiamata (istanziazione) produce dei legami elaborando la dichiarazione contenuta nel corpo dell’astrazione generica.

L’astrazione generica può essere descritta come segue:

generic I(FP1; …; FPn) is D

dove I è un identificatore, FP_1; …; FP_n sono parametri formali, e D è una dichiarazione che, quando elaborata, produrrà dei legami.

D funge da matrice dalla quale ricavare le dichiarazioni per l’istanziazione.

Una dichiarazione D può essere:

La dichiarazione di un tipo;
La dichiarazione di un modulo;
La dichiarazione di una funzione;
La dichiarazione di una procedura;

Il generic package di Ada è una esemplificazione di astrazione generica. L’espressione package ST1 is new STACK è un esempio di istanziazione generica. Le astrazioni generiche, come qualsiasi altra astrazione, possono essere parametrizzate.

In principio si può applicare l’astrazione generica a qualunque dichiarazione, incluso le procedure e le funzioni. In realtà è poco utile disporre di due funzioni identiche ma di nome diverso, invece si dichiara una generica procedure che opera su dati di tipo T qualunque, specificato al momento dell’istanziazione.

Esempio:

generic  
type T is private;  
procedure T_swap(a, b: in out T);  

procedure T_swap(a, b: in out T) is  
    tmp: T;  
    begin  
        tmp := a; 
        a := b; 
        b := tmp;  
    end T_swap;

La clausola generic introduce un parametro di tipo e la dichiarazione che segue introduce la matrice di una procedura che scambia due dati di un tipo T generico. Le procedure
effettive sono ottenute istanziando la procedura generica con i parametri di tipo effettivi da sostituire a T:

procedure int_swap is new T_swap(INTEGER)  
procedure str_swap is new T_swap(STRING)

-- utilizzo
int_swap(i, j) 
str_swap(s, t)

In questo modo si è:

Svincolato la definizione dello scambio di due elementi dal tipo degli elementi da scambiare;
Garantito comunque il controllo statico dei tipi fra parametri formali e parametri effettivi

1.8.1 Astrazione generica in C++

In C++ l’astrazione generica è supportata mediante i template.

Un template è del codice generico dotato di parametri che possono assumere valori specifici a compile-time.

Esempio:

template<class T> class provola {  
    T x;  
    public:  
        T getx() {
            return x;
        }  
        
        void setx(T y) { 
            x = y;
        }  
};

Possiamo creare due istanziazioni della classe template, usando in questo caso l’istanziazione esplicita:

template class provola<int>;
template class provola<char>;

Il compilatore genererà due definizioni di classi, una per ogni istanziazione.

Se però faccio una cosa del genere avrò errore di compilazione:

template class provola<int>;
template class provola<int>;

Si distinguono due categorie di template in C++:

Template di classe: definisce la struttura e le operazioni per un insieme illimitato di tipi correlati.
Template di funzione: definisce un insieme illimitato di funzioni correlate. (overloading)

1.8.2 Template vs Generics

La differenza è soprattutto nel modo in cui sono trattate dal compilatore.

Il compilatore C++ genera del codice specifico per ogni istanziazione del template.
Il compilatore Java introduce dei controlli al compile-time sulle classi generiche in modo da controllare le chiamate ai metodi della classe. Il codice della classe generica non è ricompilato. In Java non c’è il precompilatore.

2 Ada

2.1 Package

In Ada il modulo è chiamato package e si compone di due parti:

uno specification, che interagisce con l’ambiente esterno: contiene le dichiarazioni di tipi, costanti, procedure e funzioni. A sua volta la specification si articola in due sottoparti:
1. visible: le entità dichiarate in questa parte possono essere rese note ad altre unità di programma per mezzo della clausola use, qui ci vanno quindi le segnature delle operazioni lecite e il nome del tipo (in caso di tipo astratto). ❗Attenzione: se un costruttore non ha parametri, e questo non fa inizializzazioni particolari, non va riportato nello specification, perchè è implicitamente implementato nel linguaggio, ed equivale a dichiarare una variabile
2. private: le entità dichiarate in questa parte non possono essere nè esportate nè dichiarate nel corpo, questa parte è visibile ai package che usano il package corrente e solamente al compilatore

Se un package deve usare altri package, necessiterà quindi soltanto dello specification del package da “importare”. In più lo specification contiene tutte le informazioni necessarie al compilatore e al programmatore. Il compilatore si occupa di allocare memoria per ogni variabile, pertanto deve conoscere la rappresentazione in memoria del dato, che sarà presente nella parte private (per requisito di protezione) dello specification

un body, che contiene, fra l’altro, l’implementazione di procedure e funzioni dichiarate nello specification e tutte quelle operazioni che sono non lecite ma necessarie per realizzare le operazioni lecite, ed eventualmente una routine di inizializzazione del package (main, che viene eseguito ogni qualvolta vi è la clausola use).

2.2 Parametri formali

I parametri vengono definiti anche a seconda del loro utilizzo:

in out: posso modificare e fuori si vede la modifica
in: può essere solo letto
out: avvalorato e restituito
limited: impedisce che le operazioni di assegnazione e confronto offerte per default dal compilatore funzionino, ad esempio il confronto lavora di base byte a byte, e potrebbe non comportarsi correttamente rispetto al nostro tipo. In questo caso nell’array avremo valori sporchi quindi l’operatore byte a byte non funziona correttamente. Inoltre, se nelle specifiche l’operatore = non è riportato come operazione lecita, non deve essere consentita. Se l’operatore di confronto è previsto ma quello default non funziona correttamente, va utilizzata la clausola limited e implementata una funzione di confronto.

2.3 Tipi astratti

Di seguito riportiamo un esempio dell’implementazione del tipo astratto Stack:

package Type_stack is  
    type Stack is private  
    procedure push(s: in out Stack; x: in Integer);  
    procedure pop(s: in out Stack);  
    procedure top(s: in Stack; x: out Integer);  
    function empty(s: in Stack) return Boolean;  

private:  
    max: constant := 100;  
    type Stack is limited record  
    st: array(1..max) of Integer;  
    top: Integer range 0..max := 0;  
    end record;  
end Type_stack;

package body Type_stack is  
procedure push(s: in out Stack; x: in Integer) is  
    begin  
        s.top := s.top + 1;  
        s.st(s.top) := x;  
    end push;  

procedure pop(s: in out Stack) is  
    begin  
        s.top := s.top - 1;  
    end pop;  

procedure top(s: in Stack, x: out Integer) is  
    begin  
        x := s.st(s.top);  
    end top;  

function empty(s: in Stack) return Boolean is
    begin  
        return (s.top = 0);  
    end empty;  
end Type_stack;

Esempio di utilizzo:

(siamo nel package Pippo)
with Type_Stack; use Type_Stack;
var s: Stack
push(s, 1)
push(s, 2)
pop(s)
var s1: Stack
push(s1, 1)

NB. In questa implementazione mancano le eccezioni della semantica di restrizione. Realizziamo l’operatore pop con le eccezioni:

procedure pop(s: in out Stack) is  
    begin  
        if top > 0 then
            s.top := s.top - 1;  
        else
            raise("Eccezione")
    end pop;

Quindi, riconosciamo un Tipo astratto quando:

non vi sono variabili globali
nel body è presente un main, ma non obbligatoriamente
nello specification viene mostrato il nome del tipo

2.4 Oggetti

In Ada è possibile definire oggetti, cioè moduli dotati di stato locale, ovvero hanno delle variabili globali e il package è formato dalle segnature delle operazioni lecite senza il tipo, poichè non è mostrato il nome, e in più la parte privata non c’è perchè se non viene pubblicato il nome non ha senso mostrarne la rappresentazione in memoria

Definiamo l’oggetto Stack:

package Stack is  
    procedure push(x: in Integer);  
    procedure pop;  
    procedure top(x: out Integer);  
    function empty return Boolean;  
end Stack;

package body Stack is  
    -- qui viene rappresentato lo stack
    max: constant := 100;  
    type Table is array(1..max) of Integer;  
    st: Table;  
    top: Integer range 0..max := 0;  

procedure push(x: in Integer) is  
    begin  
        top := top + 1;  
        st(top) := x;  
    end push;  

procedure pop is  
    begin  
        top := top - 1;  
    end pop;  

procedure top(x: out Integer) is  
    begin  
        x := st(top);  
    end top;  

function empty return Boolean is
    begin  
        return (top = 0);  
    end empty;  
end Stack;

Esempio di utilizzo:

(siamo nel package Pippo)
with Stack; use Stack;

push(1)
push(2)
pop()
top(x)
put(x) -- stampa 2

Nel body quindi vi sono variabili globali, che alla fine servono per manipolare il dato, e fungono da rappresentazione in memoria dell’oggetto. Inoltre notiamo come per utilizzare le variabili non è più necessario usare la dot notation, poichè sono già presenti nel body. Il compilatore però ora dovrà compilare un package per ogni oggetto istanziato.

2.5 Classi

In Ada una classe è l’astrazione generica di un package oggetto, ovvero si definisce un package generico che identifica una classe di oggetti simili, i singoli oggetti si ottengono con il meccanismo della istanziazione della classe. In Ada si premette la parola generic alla dichiarazione del modulo per identificare un package generico. Per ottenere i singoli oggetti si utilizza package nome is new nomeClasse, seguito dalla clausola use.

A livello di compilazione, l’istanziazione viene processata dal precompilatore: va nel generic package, se ne crea una copia, toglie la keyword generic, e al posto del nome della classe ci mette il nome del singolo oggetto. Quindi non viene risolto il problema che il compilatore deve compilare un package per ogni istanziazione.

La definizione di una classe corrisponde a una particolare forma di astrazione generica, poichè l’istanziazione ha l’effetto di creare il legame tra identificatore dell’oggetto e nome della classe.

2.6 Classi/Tipi astratti generici

I parametri di tipo possono essere utilizzati anche quando si definiscono delle classi o dei tipi astratti. Di seguito un esempio di Classe:

generic  
max is Positive;  
type ITEM is private;  
package Stack is  
    procedure push(x: in ITEM);  
    procedure pop;  
    procedure top(x: out ITEM);  
    function empty return Boolean;  
end Stack;  

package body Stack is  
type Table is array(1..max) of ITEM;  
st: Table;  
top: Integer range 0..max := 0;

procedure push(x: in ITEM) is  
begin  
    top := top + 1;  
    st(top) := x;  
end push;  

procedure pop is  
begin  
    top := top - 1;  
end pop;  

procedure top(x: out ITEM) is  
begin  
    x := st(top);  
end top;

In questo caso creeremo i singoli oggetti nel seguente modo:

declare  
package STACK_INT is new STACK(10,INTEGER);  
use STACK_INT;  
package STACK_REAL is new STACK(10,REAL);  
use STACK_REAL;  

var A: REAL
var B: INTEGER 

begin  
    push(12);
    push(15.0);
    top(B);
    top(A)  
end

La dot notation è superflua perchè le chiamate a funzioni/procedure sono differenziate dal contesto (overloading).

Di seguito un esempio di tipo astratto generico:

generic
    MAX: Positive;
    type ITEM is private;
    
package STACKS is
    type STACK is limited private;
    procedure PUSH(S: in out STACK; E: in ITEM);
    procedure POP(S: in out STACK; E: out ITEM);

    private
        type STACK is record
                        ST: array(1..MAX) of ITEM;
                        TOP: integer range 0..MAX;
        end record;
end;

package body STACKS is
procedure PUSH(S: in out STACK; E: in ITEM);
    begin
    S.TOP := S.TOP – 1;
    S.ST(S.TOP) := E;
    end PUSH;
    
procedure POP(S: in out STACK; E: out ITEM);
    begin
    E := S.ST(S.TOP);
    S.TOP := S.TOP – 1;
    end POP;
end STACKS

declare
package MY_STACK is new STACKS(100, REAL);
use MY_STACK;
x: MY_STACK.STACK; I: REAL;

begin
    push(x, 175.0);
    pop(x, I)
end

2.7 Differenze tra tipi astratti e classi

Tipi astratti	Classi
Nel tipo astratto gli operatori hanno un parametro in più, relativo proprio al tipo che si sta definendo
Gli operatori sono definiti una sola volta	Gli operatori sono definiti tante volte quante sono le istanze, per via delle diverse istanziazioni
Il tipo astratto è organizzato intorno alle osservazioni, ovvero è possibile dichiarare molteplici variabili e le operazioni lavorano su esse	La classe è organizzata intorno ai costruttori, ovvero l’oggetto è una istanza, cioè un valore, e l’oggetto è definito dalla combinazione di tutte le operazioni possibili su di esso

2.8 Pro e contro del tipo astratto

Pro	Contro
Nei linguaggi imperativi, come Ada, i tipi astratti sono cittadini di prima classe, gli oggetti sono di terza classe in quanto una procedura non può restituire l’istanza di un generic package e non è possibile creare dinamicamente degli oggetti. Quindi, se ho ad esempio un operatore binario, e questo richiede come parametro un oggetto, non lo posso realizzare perchè gli oggetti non sono esprimibili	Scarsa estendibilità: l’aggiunta di un nuovo costruttore comporta dei cambiamenti nelle implementazioni degli operatori, cioè andrebbero rivisti in modo da prevedere il trattamento di rappresentazioni ottenute con nuovi costruttori. Con una classe invece, per un nuovo costruttore, basta creare una nuova classe

Nei linguaggi imperativi, come Ada, i tipi astratti sono cittadini di prima classe, gli oggetti sono di terza classe in quanto una procedura non può restituire l’istanza di un generic package e non è possibile creare dinamicamente degli oggetti. Quindi, se ho ad esempio un operatore binario, e questo richiede come parametro un oggetto, non lo posso realizzare perchè gli oggetti non sono esprimibili

Scarsa estendibilità: l’aggiunta di un nuovo costruttore comporta dei cambiamenti nelle implementazioni degli operatori, cioè andrebbero rivisti in modo da prevedere il trattamento di rappresentazioni ottenute con nuovi costruttori. Con una classe invece, per un nuovo costruttore, basta creare una nuova classe